#include <stdio.h>
#include <string.h>
#include <stdlib.h>

#define MAX_SP_NUM 256
#define RESULT_NUM 5

typedef struct 
{
    char name[256];
    int  value;
} spInfo;

spInfo spList[MAX_SP_NUM];

int results[RESULT_NUM][MAX_SP_NUM + 1];
int tmp_result[MAX_SP_NUM];
int results_index = 0;
int best_results = 0;

void trim(char* strIn, char* strOut) // support in-place opreation
{
    char *a=strIn, *b;
    while (*a == ' '||*a == '\n' || *a == '\t') a++; // ignore spaces at the beginning
    b = strIn + strlen(strIn) - 1; // get pointer pointing at the end of the line
    while (*b == ' '||*b == '\n' || *a == '\t') b--; // ignore spaces at the end
    while (a<=b) *strOut++ = *a++; // transplace
    *strOut='\0';
}

void foo(int tot_sp,int now_sp_index, int now_credit)
{
    if (best_results == RESULT_NUM) return; //skip~
    if (now_credit<=0 || now_sp_index == tot_sp ) 
    {
        if (now_credit == 0) best_results++;
        if (results_index < RESULT_NUM) 
        {
            for (int p = 0; p<= now_sp_index - 1; p++ ) results[results_index][p]=tmp_result[p];
            for (int p = now_sp_index; p< tot_sp; p++) results[results_index][p]=0;
            results[results_index][MAX_SP_NUM] = now_credit;
            results_index++;
        }
        else 
        {
            int max_remain_i = 0;
            for (int w=0;w<RESULT_NUM;w++) 
            {
                if (results[w][MAX_SP_NUM] > results[max_remain_i][MAX_SP_NUM]) max_remain_i = w;
            }
            if(now_credit<results[max_remain_i][MAX_SP_NUM]) 
            {
                for (int p = 0; p<= now_sp_index - 1; p++ ) results[max_remain_i][p]=tmp_result[p];
                for (int p = now_sp_index; p< tot_sp; p++) results[max_remain_i][p]=0;
                results[max_remain_i][MAX_SP_NUM] = now_credit;
            }
        }
        /*for(int j=0;j<now_sp_index; j++) printf("%d ",tmp_result[j]); //
        for (int p = now_sp_index; p< tot_sp; p++) printf("%d ",tmp_result[p]=0); // 
        printf("\n");*/
        return;
    }

    for (int i = now_credit/spList[now_sp_index].value; i >= 0 ; i--)
    {
        tmp_result[now_sp_index]=i;
        foo(tot_sp, now_sp_index+1, now_credit - spList[now_sp_index].value*i);
    }
}

int load_spList(const char* filePath)
{
    FILE *fp = fopen(filePath,"r");
    char sp_info_line[512];
    int item_cnt = 0;
    while(!feof(fp))
    {
        fgets(sp_info_line, sizeof(sp_info_line), fp);
        
        if (sp_info_line[0] =='\n') continue; // ignore empty lines

        char *src = sp_info_line;
        char *dst = spList[item_cnt].name;

        trim(sp_info_line, sp_info_line); // ignore line spaces

        while (*src != '=') *(dst++) = *(src++); // copy item name
        *dst = '\0';
        src++;

        while(*src == ' ' || *src == '\t') src++;
        spList[item_cnt].value = atoi(src);

        item_cnt++;
    }
    fclose(fp);
    return item_cnt;
}

int main()
{
    // 加载并输出商品信息
    printf("# Items: \n");
    int tot_sp = load_spList("splist.txt");
    for (int i = 0; i < tot_sp; i++) printf("%5d | %s\n", spList[i].value, spList[i].name);

    printf("# Total %d items;\n",tot_sp);
    
    int m;
    printf("# Please input the credits you've got: ");
    scanf("%d",&m);
    
    foo(tot_sp,0,m);
    printf("\n");

    int cnt = 1;
    for(int i=0;i<results_index;i++)
    {
    	if(results[i][MAX_SP_NUM]==m) continue; //ignore when no credits used
        
        printf("# Plan %d:\n",cnt++);
        int remain = m;
        for(int j = 0; j < tot_sp; j++) 
        {
            if (results[i][j] == 0) continue;
            printf("- %-5d * %s\n", results[i][j], spList[j].name);
            remain -= results[i][j] * spList[j].value;
        }
        printf ("# Remain credits: %d\n", remain);
        printf("\n");
    }
    return 0;
}
